# 见书P74 用哈希查找算法查找七色光颜色
class HashTable:
    def __init__(self):
        self.size = 11
        # 槽位
        self.throw = [None] * self.size
        # 值位
        self.data = [None] * self.size

    def get_hash_value(self, key):
        return key % self.size

    def get_rehash_value(self, old_hash_value):
        return (old_hash_value + 1) % self.size

    def put(self, key, value):
        hash_value = self.get_hash_value(key)
        # 如果哈希值对应的槽为空, 直接存
        if self.throw[hash_value] is None:
            self.throw[hash_value] = key
            self.data[hash_value] = value
        # 如果不为空 看是否存在相等值 如果存在就覆盖
        else:
            if self.throw[hash_value] == key:
                self.data[hash_value] = value
                # 哈希值对应的槽不为空, 且槽中保存的key值与传入的key不相同 让key+1重新计算哈希值
            else:
                next_slot = self.get_rehash_value(hash_value)
                while self.throw[next_slot] is not None and self.throw[next_slot] != key:
                    next_slot = self.get_rehash_value(next_slot)
                if self.throw[next_slot] is None:
                    self.throw[next_slot] = key
                    self.data[next_slot] = value
                else:
                    self.data[next_slot] = value

    # 根据key值获取value值

    def get(self, key):
        # 先将key做hash, 如果没有, 返回None
        hash_value = self.get_hash_value(key)
        if hash_value is None:
            return None
        # 如果有 且key与槽中的key相等, 返回value
        if self.throw[hash_value] == key:
            return self.data[hash_value]
        # 如果有 且key与槽中的key不等, 重新hash, 直到找到相等的key返回value,如果又回到最早的hash值还没找到就返回None
        next_slot = self.get_rehash_value(hash_value)
        while self.throw[next_slot] != key:
            print(f'next_slot={next_slot}')
            next_slot = self.get_rehash_value(next_slot)
            if next_slot == hash_value:
                return None
        return self.data[next_slot]

    def print(self):
        for index, i in enumerate(range(self.size)):
            print(f'{index}  {self.throw[i]}: {self.data[i]}')

    def __setitem__(self, key, value):
        return self.put(key, value)

    def __getitem__(self, key):
        return self.get(key)


if __name__ == '__main__':
    hash_table = HashTable()
    hash_table[16] = "red"
    hash_table[28] = "orange"
    hash_table[32] = "yellow"
    hash_table[14] = "green"
    hash_table[56] = 'qing'
    hash_table[36] = 'blue'
    hash_table[71] = 'purple'
    hash_table.print()
    key = 71
    print(f'key = {key}, value = {hash_table[key]}')
